/*************************************************
 *	文件名称：mydataexample.c
 *	文件说明：本代码为mydataexample.h的函数实现，需要
			  和mydataexample.h一起编译
 *	程序平台：for linux
 *	文件作者：Jason <jasonsunsoft@163.com>
 *	文件时间：
*************************************************/
#include <stdio.h>
#include "mydata.h"


Status equal(ElemType e1, ElemType e2)
{
	return (e1 == e2);
}

Status PrinElem(ElemType e)
{
	printf("%d ", e);
	return OK;
}

//操作结果：构造一个空的线性表L。
Status InitList_Sq(SqList *L )
{
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (! L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}	//InitList_Sq

//初始条件：线性表L已存在
//操作结果：销毁线性表L。
Status DestroyList_Sq(SqList *L)
{
	if (L->elem == NULL)
		return  ERROR;
	free(L->elem );
	L->elem = NULL;
	L->length = 0;
	L->listsize = 0;
	return OK;
}	//DestroyList_Sq

//初始条件：线性表L已存在
//操作结果：将L重置为空表。
Status ClearList_Sq(SqList *L)
{
	if (L->elem == NULL)
		return  ERROR;
	free(L->elem );
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (! L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}	//ClearList_Sq

//初始条件：线性表L已存在
//操作结果：若L为空表，则返回TRUE，否则返回FALSE。
Status ListEmpty_Sq(SqList L)
{
	if ( L.elem == NULL)
		return  ERROR;
	if (!L.length)
		return TRUE;
	else
		return FALSE;
}	//ListEmpty_Sq

//初始条件：线性表L已存在
//操作结果：返回L中数据元素个数
int ListLength_Sq(SqList L)
{
	return L.length;
}

//初始条件：线性表L已存在,1 <= i <= ListLength( L)。
//操作结果：用 e 返回L中第i个元素的值。
Status GetElem_Sq(SqList L, int i, ElemType *e)
{
	if ((L.elem == NULL) || i < 1 || i > L.length)
	{
		e = NULL;
		return  ERROR;
	}
	*e = L.elem[i - 1];
	return OK;
}	//GetElem_Sq

//初始条件：线性表L已存在,compare()是元素判定函数。
//操作结果：返回L中第一个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType))
{
	int i = 0;
	while (i < L.length && !(*compare)(L.elem[i], e))
		i++;
	if (i < L.length)
		return (i + 1);
	else
		return ERROR;
}	//LocateElem_Sq


//初始条件：线性表L已存在。
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
Status PrioElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e)
{
	int Ln, i;
	if ( L.elem == NULL)
		return  ERROR;
	//Ln = ListLength_Sq(L);
	Ln = L.length;
	for (i = 1; i < Ln; i++)
	{
		if (L.elem[i] == cur_e)
		{
			*pre_e = L.elem[i - 1];
			return OK;
		}

	}
	return ERROR;
}	//PrioElem_Sq

//初始条件：线性表L已存在。
//操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e)
{
	int Ln, i;
	if ( L.elem == NULL)
		return  ERROR;
	Ln = ListLength_Sq(L);
	for (i = 0; i < (Ln - 1); i++)
	{
		if (L.elem[i] == cur_e)
		{
			*next_e = L.elem[i + 1];
			return OK;
		}

	}
	return ERROR;
}	//NextElem_Sq

//初始条件：线性表L已存在，1 <= i <= ListLength(L) + 1。
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status  ListInsert_Sq(SqList *L, int i, ElemType e)
{
	ElemType * newbase, *p, *q;
	if ((L->elem == NULL) || i < 1 || i > L->length + 1)
		return  ERROR;
	if (L->length >= L->listsize)
	{
		newbase = (ElemType *) realloc((void *)L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
		if (!newbase)
			exit(OVERFLOW);
		L->elem = newbase;
		L->listsize += LISTINCREMENT;
	}
	p = &(L->elem[i - 1]);
	for (q = &(L->elem[L->length - 1]); q >= p; q--)
		*(q + 1) = *q;		//元素右移一位
	*p = e;
	++L->length;
	return OK;
}	//ListInsert_Sq

//初始条件：线性表L已存在且非空，1 <= i <= ListLength(L)。
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status  ListDelete_Sq(SqList *L, int i, ElemType *e)
{
	ElemType * p, *q;
	if ((L->elem == NULL) || i < 1 || i > L->length)
		return  ERROR;					//判断输入是否合法
	p = &(L->elem[i - 1]);				//p为被删除的元素位置
	*e = *p;							//被删除值付给e
	q = L->elem + L->length - 1;		//表尾元素位置
	for ( ; p < q; p++)					//被删除元素左移
        *p = *(p + 1);
    --L->length;						//长度减一
    return OK;
}

//初始条件：线性表L已存在。
//操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，操作失败。
Status  ListTraverse_Sq(SqList L, Status (*visit)(ElemType e))
{
	int len, i;
	len = L.length;
	for (i = 0; i < len; i++)
	{
		if (!(*visit)(L.elem[i]))
			return ERROR;
	}
	return OK;
}

//初始条件：线性表La、Lb已存在。
//操作结果：将所有在线性表Lb中但不在La中的数据元素插入到La中
void Union_Sq(SqList *La, SqList *Lb)
{
	int La_len, Lb_len, i;
	ElemType e;
	La_len = ListLength_Sq(*La);
	Lb_len = ListLength_Sq(*Lb);
	for (i = 1; i <= Lb_len; i++)
	{
		GetElem_Sq(*Lb, i, &e);
		if (!LocateElem_Sq(*La, e, equal))
			ListInsert_Sq(La, ++La_len, e);
	}
}

//初始条件：线性表La、Lb已存在， 且线性表La和Lb中的元素值按非递减排列。
//操作结果：并归La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列
void MergelList_Sq(SqList La, SqList Lb, SqList *Lc)
{
	ElemType *pa, *pb, *pc, *pa_last, *pb_last;

	pa = La.elem;
	pb = Lb.elem;
	Lc->listsize = Lc->length = La.length + Lb.length;
	pc = Lc->elem = (ElemType *)malloc(Lc->listsize * sizeof(ElemType));
	if (!Lc->elem)
		exit(OVERFLOW);
	pa_last = La.elem + La.length - 1;
	pb_last = Lb.elem + Lb.length - 1;
	while (pa <= pa_last && pb <= pb_last)
	{
		if (*pa <= *pb)
			*pc++ = *pa++;
		else
			*pc++ = *pb++;
	}
	while (pa <= pa_last)
		*pc++ = *pa++;
	while (pb <= pb_last)
		*pc++ = *pb++;
}	//MergelList_Sq

